class Solution:
    """
    跟最小路径和很相似，每次只能向下和向右走一步，再用贪心得到是向下走还是向右走
    状态转移方程：dp[i][j] = dp[i][j] + min(dp[i+1][j], dp[i+1][j+1])
    """
    @staticmethod
    def minimum_total(triangle):
        dp = triangle
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[i][j] += min(dp[i+1][j], dp[i + 1][j + 1])
        return dp[0][0]


if __name__ == '__main__':
    m = [[2], [3, 4], [5, 6, 7], [4, 1, 8, 3]]
    print(Solution().minimum_total(m))
